/*
题目:矩阵中的最长递增路径
给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度。

对于每个单元格，你可以往上，下，左，右四个方向移动。 你 不能 在 对角线 方向上移动或移动到 边界外（即不允许环绕）。

https://leetcode.cn/problems/longest-increasing-path-in-a-matrix/submissions/
 */
public class LongestIncreasingPath {
    int[][] memo = null;
    int[] dir = new int[] {0, -1, 0, 1, 0};
    int row, col;

    public int longestIncreasingPath(int[][] matrix) {
        // 记忆化搜索
        row = matrix.length;
        col = matrix[0].length;
        memo = new int[row][col];

        int src = 0;
        for (int i = 0; i < row; i ++) {
            for (int j = 0; j < col; j ++) {
                // 以每一个点为 起点 计算最长递增路径
                src = Math.max(src, dfs(matrix, i, j));
            }
        }

        return src;
    }

    private int dfs(int[][] matrix, int x, int y) {
        if (memo[x][y] != 0) {
            return memo[x][y];
        }

        int src = 1;
        for (int i = 0; i < 4; i ++) {
            int nextX = x + dir[i];
            int nextY = y + dir[i + 1];

            // 有效 且 递增
            if (nextX >= 0 && nextX < row && nextY >= 0 && nextY < col && matrix[x][y] < matrix[nextX][nextY]) {
                src = Math.max(src, dfs(matrix, nextX, nextY) + 1);
            }
        }

        return memo[x][y] = src;
    }
}
